package com.github.yangyishe.p100;

import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵
 * https://leetcode.cn/problems/spiral-matrix/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 * 示例 2：
 *
 *
 * 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
 * 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
 *
 *
 * 提示：
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 10
 * -100 <= matrix[i][j] <= 100
 */
public class Problem54 {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {1,2,3,4},
        {5,6,7,8},
            {9,10,11,12}
        };

        Problem54 problem54 = new Problem54();
        List<Integer> integers = problem54.spiralOrder(matrix);
        System.out.println(integers);
    }

    /**
     * 思路:
     * 任意时刻遍历, 都应该确定其遍历方向. 只要遍历方向正确, 则最后必定能按照螺旋方式进行遍历
     * 遍历方向受两个要素影响:
     * 1. 当前正在的遍历方向(上一次遍历方向)
     * 2. 是否抵达边界. 边界是一个记录上下左右的数组索引记录
     *
     * 没有抵达边界时, 遍历方向总是与上一次一致;
     * 抵达边界时, 遍历方向按照R->B->L->T->R的方向变更; 同时分别对R,B,L,T的边界值进行记录
     *
     * 如果变更的边界值R==L或B==T时, 遍历结束
     *
     * 注: 矩阵中, 很重要的一个问题是, 一定要区分号好行列. 第一个索引是列序号, 第二个索引是行序号
     *
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int rl=matrix[0].length-1;
        int bl=matrix.length-1;
        int ll=0;
        int tl=0;

        char d='R';

        int row=0;
        int col=0;
        List<Integer> resultList=new ArrayList<>((rl+1)*(bl+1));
        while(true){
            // 每次转换方向, 边界值马上就会发生变化.
            if(rl<ll||bl<tl){
                return resultList;
            }
            // 记录当次值
            resultList.add(matrix[row][col]);
            // 根据上一次标记前进
            if(d=='R'){
                if(col<rl){
                    col++;
                }else{
                    row++;
                    d='B';
                    tl++;
                }
            }else if(d=='B'){
                if(row<bl){
                    row++;
                }else{
                    col--;
                    d='L';
                    rl--;
                }
            }else if(d=='L'){
                if(col>ll){
                    col--;
                }else{
                    row--;
                    d='T';
                    bl--;
                }
            }else{
                if(row>tl){
                    row--;
                }else{
                    col++;
                    d='R';
                    ll++;
                }
            }
        }



    }
}
